import javax.imageio.stream.IIOByteBuffer;
import java.util.Arrays;
import java.util.Stack;

public class TestSort {
    /*
        直接插入排序：数组向后遍历，大的往后移
        时间复杂度为O(N^2)，但是数组越有序越快，空间复杂度：O(1)
        它是一个稳定的排序
     */
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++){
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--){
                if (arr[j] > tmp){
                    arr[j + 1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }

    /*
        希尔排序：分组进行直接插入排序
        时间复杂度：O(N^1.3 - N^1.5)，空间复杂度：O(1)
        稳定性：不稳定
     */
    public static void shell(int[] array, int gap){
        for (int i = gap; i < array.length; i++){
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap){
                if (array[j] > tmp){
                    array[j + gap] = array[j];
                }else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            shell(array, gap);
            gap /= 2;
        }
        shell(array, 1);
    }

    /*
        选择排序：从后面选择一个最小的放到前面
        时间复杂度：O(N^2)，空间复杂度：O(1)
        稳定性：不稳定
     */
    public static void selectSort1(int[] array){
        for (int i = 0; i < array.length; i++){
            for (int j = i + 1; j < array.length; j++){
                if (array[j] < array[i]){
                    int tmp = array[j];
                    array[j] = array[i];
                    array[i] = tmp;
                }
            }
        }
    }
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++){
            int min = i; //i之前都排好序了
            for (int j = i + 1; j < array.length; j++){
                if (array[j] < array[min]){
                    min = j;
                }
            }
            int tmp = array[i];
            array[i] = array[min];
            array[min] = tmp;
        }
    }

    /*
        堆排序：先把数组变为大根堆，再堆排序
        时间复杂度：O(N * logN)，空间复杂度：O(1)
        稳定性：不稳定
     */
    public static void heapSort(int[] array){
        //创建堆时间复杂度是O(N)
        createHeap(array);
        int end = array.length - 1;
        while (end > 0){
            //遍历并调整时间复杂度为O(N * logN)
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            shiftDown(array, 0, end);
            end--;
        }
    }
    public static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >= 0; parent--){
            shiftDown(array, parent, array.length);
        }
    }
    public static void shiftDown(int[] array, int parent, int len){
        int child = parent * 2 + 1;
        while (child < len){
            //有没有右孩子，右孩子大不大
            if (child + 1 < len && array[child + 1] > array[child]){
                child++;
            }
            //判断要不要父子交换
            if (array[parent] < array[child]){
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                //换完parent到child位置
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

    /*
        冒泡排序：
        时间复杂度：O(N^2)，优化后最好为O(N)，空间复杂度：O(1)
        稳定性：稳定
     */
    public static void bubbleSort(int[] array){
        //i代表趟数
        for (int i = 0; i < array.length - 1; i++){
            boolean flg = false;//优化
            //j代表每趟比较次数
            for (int j = 0; j < array.length - i - 1; j++){
                if (array[j] > array[j + 1]){
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flg = true;
                }
            }
            //如果flg是false证明没有交换，说明已经有序了
            if (!flg){
                break;
            }
        }
    }

    /*
        快速排序：找到一个基准，左边一定小于基准，右边一定大于基准，再递归
        时间复杂度：O(N*logN)，最坏情况下就是有序时会达到O(N ^ 2)（每次都要遍历N次，一共要树的高度次）
        空间复杂度：O(logN)（树的高度），最坏同上，会形成单分支的树，达到O(N)
        稳定性：不稳定
     */
    public static void quickSort(int[] array){
        quick(array, 0, array.length - 1);
    }
    public static void insertSort1(int[] arr,int left, int right){
        for (int i = left + 1; i <= right; i++){
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= left; j--){
                if (arr[j] > tmp){
                    arr[j + 1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }
    public static void quick(int[] array, int left, int right){
        //结束递归条件
        if (left >= right){
            return;
        }
        //如果区间缩小到一定值可以直接用插入排序
        if (right - left + 1 <= 30){
            insertSort1(array, left, right);
            return;
        }
        //三数取中法找基准
        int midIndex = findMid(array, left, right);
        int tmp = array[left];
        array[left] = array[tmp];
        array[tmp] = array[left];
        //找到基准
        int pivot = partition(array, left, right);
        //递归左边
        quick(array, left, pivot - 1);
        //递归右边
        quick(array, pivot + 1, right);
    }
    public static int findMid(int[] array, int left, int right){
        int mid = left + (right - left) / 2;
        if (array[left] > array[right]){
            if (array[left] < array[mid]){
                return left;
            }else {
                if (array[right] > array[mid]){
                    return right;
                }else {
                    return mid;
                }
            }
        }else {
            if (array[left] > array[mid]){
                return left;
            }else {
                if (array[right] < array[mid]){
                    return right;
                }else {
                    return mid;
                }
            }
        }
    }
    public static int partition(int[] array, int start, int end){
        //挖坑法：
        int tmp = array[start];
        while (start < end){
            //找到右边比tmp小的(等于如果不加，会重复赋值)
            while (start < end && array[end] >= tmp){
                end--;
            }
            //找到小的就放过去
            array[start] = array[end];
            //找到左边比tmp大的
            while (start < end && array[start] <= tmp){
                start++;
            }
            array[end] = array[start];
        }
        //start和end相遇后别忘了把最后的tmp赋值过来
        array[start] = tmp;
        return start;
    }
    //最后再写一种非递归的写法：
    public static void quickSort1(int[] array){
        //递归的本质就是用栈，这里我们用栈来写
        //划分之后，把左右数对放入栈中，此时还要判断是不是pivot左右只剩下一个元素
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array, left, right);//先找到一个基准
        if (pivot > left + 1){
            //左边数大于两个
            stack.push(left);
            stack.push(pivot - 1);
        }
        if (pivot < right - 1){
            //右边数大于两个
            stack.push(pivot + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array, left, right);
            if (pivot > left + 1){
                //左边数大于两个
                stack.push(left);
                stack.push(pivot - 1);
            }
            if (pivot < right - 1){
                //右边数大于两个
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }

    /*
        归并排序：
        时间复杂度：O(logN * N)
        空间复杂度：O(N)
        稳定性：稳定
     */
    public static void mergeSort(int[] array){
        mergeSortInternal(array, 0, array.length - 1);
    }
    public static void mergeSortInternal(int[] array, int left, int right){
        if (left >= right){
            return;
        }
        int mid = left + (right - left) / 2;
        //左边
        mergeSortInternal(array, left, mid);
        //右边
        mergeSortInternal(array, mid + 1, right);
        //合并
        merge(array, left, mid, right);
    }
    public static void merge(int[] array, int left, int mid, int right){
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int k = 0;
        int[] ans = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2){
            if (array[s1] <= array[s2]){//这里 '=' 不加就不稳定了
                ans[k++] = array[s1++];
            }else {
                ans[k++] = array[s2++];
            }
        }
        //第一个数组还有元素
        while (s1 <= e1){
            ans[k++] = array[s1++];
        }
        //第二个数组还有元素
        while (s2 <= e2){
            ans[k++] = array[s2++];
        }
        //将ans中的元素放入array中
        for (int i = 0; i < ans.length; i++) {
            array[i + left] = ans[i];
        }
    }
    //非递归实现:
    public static void mergeSort1(int[] array){
        int nums = 1;
        while (nums < array.length){
            for (int i = 0; i < array.length; i += nums * 2){
                int left = i;
                int mid = left + nums - 1;
                //防止越界
                if (mid >= array.length){
                    mid = array.length - 1;
                }
                int right = nums + mid;
                if (right >= array.length){
                    right = array.length - 1;
                }
                merge(array, left, mid, right);
            }
            nums *= 2;
        }
    }

    /*
        计数排序：用一个数组记录每个数出现次数，最后按次数打印出来
        适用于有N个数，数据范围为0~N之间
        时间复杂度：O(N)
        空间复杂度：O(M) M代表数据范围
        稳定性：此代码不稳定，本质可以实现稳定
     */
    public static void countingSort(int[] array){
        int minVal = array[0];//找到最小值
        int maxVal = array[0];//找到最大值
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal){
                maxVal = array[i];
            }
            if (array[i] < minVal){
                minVal = array[i];
            }
        }
        //找到最大值和最小值后相减 +1 就是数组长度
        int[] count = new int[maxVal - minVal + 1];
        //再统计每个数出现的次数
        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            count[index - minVal]++;//这里有可能不是从0开始
        }
        //把count计数器逐个放到array中
        int j = 0;
        for (int i = 0; i < array.length; i++) {
            while (count[i] > 0){
                array[j++] = i + minVal;//这里同理，不一定是i出现了count[i]次
                count[i]--;
            }
        }
    }


    public static void main(String[] args) {
        int[] arr = {1,3,5,0,4,7,9,8,2,0};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}